#include <iostream>
using namespace std;

// Definition for singly-linked list.
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
public:
    bool hasCycle(ListNode *head) {
        if (head == nullptr || head->next == nullptr) {
            return false; // 如果链表为空或者只有一个节点，则肯定没有环
        }
        
        ListNode *fast = head;
        ListNode *slow = head;
        
        while (fast != nullptr && fast->next != nullptr) {
            fast = fast->next->next; // 快指针每次走两步
            slow = slow->next;       // 慢指针每次走一步
            
            // 如果快指针追上了慢指针，说明有环
            if (fast == slow) {
                return true;
            }
        }
        
        return false; // 遍历完链表也没有发现环
    }
};

// 测试函数
int main() {
    // 创建链表节点
    ListNode *head = new ListNode(3);
    ListNode *second = new ListNode(2);
    ListNode *third = new ListNode(0);
    ListNode *fourth = new ListNode(-4);

    // 构建带环的链表
    head->next = second;
    second->next = third;
    third->next = fourth;
    fourth->next = second; // 形成环：-4 -> 2

    // 创建 Solution 对象
    Solution solution;
    
    // 检测链表是否有环
    bool hasCycle = solution.hasCycle(head);

    // 打印结果
    if (hasCycle) {
        cout << "The linked list has a cycle." << endl;
    } else {
        cout << "The linked list does not have a cycle." << endl;
    }

    // 释放链表的内存（释放节点）
    delete fourth;
    delete third;
    delete second;
    delete head;

    return 0;
}
